package orderstatics;

import java.util.Random;

public class OrderStatics {
    private static int max;
    private static int min;

    /**
     * get max and min value but use just one polling
     * @param A array to be found out the max and the min value
     */
    public static void getMaxMin(int[] A) {
        if(A.length < 1) {
            System.out.println("A is an empty array");
            return ;
        }

        int p = 0; // next compare start location
        // set initial value of max, min to ensure left number of element of array A is even
        if (0 == A.length % 2) { // even number
            if(A[0] >= A[1]) {
                max = A[0];
                min = A[1];

            }
            else {
                max = A[1];
                min = A[0];
            }
            p = 2;
        }
        else { // odd number
            max = A[0];
            min = A[0];
            p = 1;
        }

        int larger;
        int smaller;
        // n / 2 group (A[i] and A[i+1]). larger between two element compare to current max, smaller compare to current min
        for (int i = p; i < A.length - 1; i = i+2) {

            if(A[i] >= A[i+1] ) {
                larger = A[i];
                smaller = A[i+1];
            }
            else {
                larger = A[i+1];
                smaller = A[i];
            }

            if (larger > max) max = larger;
            if (smaller < min) min = smaller;
        }

        // print result, value of max and min
        System.out.println("max = " + max);
        System.out.println("min = " + min);
    }

    /**
     * select the max value of A.
     * @param A array to be found out the max
     * @param p start index
     * @param r end index
     * @return the max value
     * @apiNote  T(n) = O(logn)
     */
    public static int selectMax(int A[], int p, int r) {
        if(p < r) {
            int q = (p + r) >> 1;
            int leftMax = selectMax(A, p, q);
            int rightMax = selectMax(A, q+1, r);
            return Math.max(leftMax, rightMax);
        }
        else return A[p];
    }

    /**
     * select the i-th min value
     * @param A data array to be selected
     * @param p start index
     * @param r end index
     * @param i indicate the i-th min of A
     * @return the i-th min
     */
    public static int randomizedSelect(int[] A, int p, int r, int i) {
        if (p == r) return A[p];

        int q = randomizedPartition(A, p, r);
        int k = q - p + 1;

        if (i == k) return A[q];
        else if (i < k) return randomizedSelect(A, p, q-1, i);
        else return randomizedSelect(A, q+1, r, i - k);
    }

    private static void exchange(int[] A, int d1, int d2) {
        int temp = A[d1];
        A[d1] = A[d2];
        A[d2] = temp;
    }

    private static int partition(int[] A, int p, int r) {
        int x = A[r];
        int i = p - 1;
        for (int j = p; j < r; j++) {
            if(A[j] <= x) {
                i ++;
                exchange(A, i, j);
            }
        }
        exchange(A, i+1, r);
        return i+1;
    }

    public static int randomizedPartition(int[] A, int p, int r) {
        System.out.println("p=" +p+", r=" + r);
        System.out.println("r-p = " + (r-p));
        int i = new Random().nextInt(r-p) + p;
        System.out.println("i=" +i + ", r="+r + ", A.length=" + A.length);

        exchange(A, i, r);

        return partition(A, p, r);
    }
}
